INTRODUCTION:

Multicasting in ad hoc networks is more complex than in wired networks, because of host mobility, interference of wireless signals, and the broadcast nature of the communication. There are two ways we can classify the multicasting protocols: source-based and core based. In a source-based protocol, each source maintains a multicast tree to every Member in the multicast group. Thus, multiple multicast trees exist in the network.

Even though multicasting can be achieved with multiple unicast routing, the traffic could block the network, especially the resource-restricted ad hoc networks. Energy is a sensitive issue in these networks, since the nodes lack constant power supply. Packet trans receiving consumes energy in ad hoc networks, since a packet can be routed through many intermediate nodes before reaching its destination. Because the nodes in an ad hoc network have limited power supply, it is vital to be able to find mechanisms and protocols that optimize the usage of battery power and thus increase the lifetime of the network.

Existing Protocols: Most of the existing multicast routing protocols are extension of an unicast routing algorithm. They differ in the management of multicast groups as well as the multicast tree construction. In regard to group management, they can rely on a centralized policy (e.g. M-AODV) or a distributed one (e.g. M-OLSR). The tree may be constructed using a proactive vision (e.g. M-OLSR) or a reactive one (e.g. M-AODV). In this section, we describe two protocols, M-AODV and M-OLSR, both of them based on well-known unicast routing protocols, respectively AODV and OLSR. Other adhoc multicast routing protocols are available, like DDM¹², ODMRP⁸, AMR² or AMRIS¹⁶. The adhoc unicast routing protocol AODV⁴ is a reactive protocol. Routes are built on demand using a route discovery mechanism. To initiate a communication a node floods the network with a route request control packet RREQ. To this request may respond the destination as well as all nodes having knowledge of a route to the destination? They send to the source a route reply control packet RREP which activates the route along its way

The multicast integration in AODV is based on the route request and reply mechanism provided by the unicast protocol. Group management is dynamic: nodes may join and leave a group without any constraint. A leader is associated to each group and it is in charge of the management of crucial topology changes. In order to spread multicast data, Multicast AODV (M-AODV¹⁵) maintains a bidirectional multicast tree. Branches of multicast trees are dynamically created when a node joins the group. Such a node sends a RREQ with the multicast address as destination address.

Evaluation of adhoc multicast trees

To confront these early theoretical remarks, to practically evaluate tree construction algorithms and to find which policies are the most adapted to adhoc networks, we have statically simulated several algorithms and evaluated the resulting diffusion structures. Multicast algorithms were simulated using a class of randomly generated graphs, random geometric graphs. Evaluations were realized using several criteria that we have chosen in adaptation to the adhoc environment

Evaluation criteria for adhoc trees: Classical criteria usually used to evaluate multicast trees in wire networks are not well-adapted to an adhoc environment. Examples of criteria (see [6] for a detailed description) are the number of edges, the reach cost or the communication time. If they may give an appropriate view of diffusion structure performance (latency or bandwidth of the tree), they cannot be interpreted in terms of packet collisions or radio occupation. They also do not provide any information about the number of adhoc nodes solicited to route the multicast flow. In a cooperative environment like an adhoc network, it may be important to minimize the number of routing nodes that are not interested in the multicast data.

We propose a comparison adhoc multicast trees using the six following criteria:

• Collateral receivers: number of non group members receiving the multicast packet.

• Active receivers: number of group members receiving the multicast packet.

. Collateral transmitters: number of non group members emitting the multicast packet.

• Active transmitters: number of group members emitting the multicast packet.

• Collateral hits: number of times a multicast packet reaches a non group member.

• Active hits: number of times a multicast packet reaches a group member.

A node enters the receiver category if it receives at least once a multicast packet, i.e. if it is the neighbor of a tree internal node. It enters the transmitter’s one if it is a tree internal node. Finally a node is counted as an hit every times it receives a multicast packet. It is a collateral node if it does not belong to the multicast group and an active one if it does. Collateral values are interesting since they give a good overview of the load the multicast flow induces in the network.

Problem Statement In a multi-hop mobile ad-hoc network, mobile nodes cooperate to form a network without using any infrastructure such as access points and base stations. Instead, the mobile nodes forward packets for each other’s allowing communication among nodes outside wireless transmission range. Examples of applications for ad-hoc networks range from military operation and emergency disaster relief to community networking and interaction among meeting attendees or students during a lecture. In these ad-hoc networking applications, security is necessary to guard the network from various types of attacks. In ad-hoc networks, adverse nodes can freely join the network, listen to and/or interfere with network traffic, and compromise network nodes leads to various network failures¹. Since routing protocols are a fundamental tool of network-based computation, attacks on unsecured routing protocols can disrupt network performance and reliability Multicasting is a more efficient method of supporting group communication, as it allows transmission and routing of packets to multiple destinations with fewer network resources. Multicasting can improve the efficiency of the wireless links, when sending multiple copies of messages, by exploiting the inherent broadcast property of the wireless medium when multiple mobile nodes are located within the transmission range of a node. Providing efficient multicasting over MANET faces many challenges, including dynamic group membership and constant update of delivery path due to node movement².

State management of multicast protocols involves timely updating of the multicast routing tables at the involved nodes to maintain the correctness of the multicast routing structure, tree or mesh, according to the current network topology. Even under moderate node mobility and multicast member size, state management incurs considerable amount of control traffic. When the group size grows, and/or number of groups increase, traditional tree or mesh based methods^22-25 become inefficient. To address the scalability issues, we need to reduce the protocol states and constrain their distribution, or even use methods that do not need to have protocol state. A number of research efforts have adopted this method, which can be classified into the following categories: overlay multicasting, backbone-based multicasting and stateless multicasting. We study these different approaches for constraining protocol states, and their scalability issues.

Fig 1: A multicast transmission in an ad hoc network

Proposed Approach NAMP is an efficient tree-based multicast routing protocol which also includes the neighboring concept. The routes are built and maintained using the traditional request and reply messages. A hard state approach is used for multicast group maintenance. NAMP uses neighbor information of two-hops away for transmitting the packets to the receiver(s). If the receiver(s) is not within this range, then it searches the receiver(s) using dominant pruning flooding method and forms the multicast group using the replies along the reverse path. Although the mesh structure is known to be more robust against topological changes, the tree structure is better in terms of packet transmission. NAMP targets to achieve less end-to-end delay of packets by using a tree structure and it uses the secondary forwarder list method for robustness.

Each node vi keeps the information of all of its neighbors of one-hop distance in a neighbor table. A node periodically transmits HELLO packet (containing its own neighbor table information) to all of its neighbors. If there is already an existing neighbor node vj, it gets the HELLO packet of vi, in which its vj own ID is included. Consequently, node vi also gets the HELLO packet from node vj that is, the neighboring information of node vj. If a neighbor node vj moves out of the range of node vi, NAMP uses a soft-state. approach (e.g., a time out value is assigned to each entry of the neighbor table) to detect the topological change. If a node comes within the neighbor range of another node for the first time, it gets the HELLO packet of that node and finds that its own ID is missing but as it is now within the neighbor range, it informs about its presence by sending a HELLO_REP packet and eventually the neighbor table of each node is updated.

Multicast Tree Creation When a source wants to send a data packet, it initializes a FLOOD_REQ packet with data payload attached. This packet is flooded throughout the network based on dominant Pruning method. We first state the dominant pruning approach and then show how it is used in NAMP. Dominant pruning approach extends the range of neighborhood information into two-hop apart nodes. This two-hop neighborhood knowledge can be obtained by exchanging the adjacent node lists with neighbors. In dominant pruning, the sender node selects adjacent nodes that should relay the packet to complete broadcast. The IDs of selected adjacent nodes are recoded in the packet as a forward list. An adjacent node that is requested to relay the packet again determines the forward list. This process is iterated until broadcast is completed. N (v) implies the set of adjacent nodes of node v while N (N (v)) is the set of nodes at most two-hops apart from node v. Both sets include the node v itself.

Let us examine how each node determines the forward list. Suppose, node vj receives a packet from vi and vj is in the forward list. Node vj should determine its own forward list so that all nodes within two-hop distance from vj receive the packet. The forward list should be minimized to decrease the number of transmissions. Among nodes in N(N(vj)), vi, vj, N(vi) have already received the packet, and N(vj) will receive the packet when vj forwards the packet. Therefore, a node vj determines its forward list so that all nodes in U = N(N(vj))- N(vi)- N(vj) receive the packet 1. Let B(vi, vj) = N(vj)– N(vi). Then a set of ⊆ nodes F = {f1, f2 ,… fm} B (vi , vj ) is selected such that Ufi Є F (N(fi)∩U)= U.

Finding a minimum F is the set cover problem which is NP-complete. Thus, approximation algorithms are used to determine the forward list. Dominant pruning flooding uses greedy set cover algorithm. The algorithm which finds the set F is as follows:

Let F = 0, K = {S1, S2…Sn} where, Sk = N(vk) ∩ U(I ≤ k≤ n), Z = 0

Find the set Sk whose size is maximal in a set K.

F = FU {vk }, Z = ZU Sk , K = K – {Sk}, St = St – Sk for all St Є K

If Z = U, complete the algorithm

Otherwise, repeat from 2 again.

This algorithm repeats selecting vk in which the number of neighbor nodes that is not covered yet is maximum. It has been proved that, this approximation algorithm has the approximation ratio of (ln |U|+ 1)¹⁹. Let us explain dominant pruning with an example shown in Figure 2. In the figure, node 4 is the source node. Blind flooding needs eight packets forwarding because all the nodes that receive the packet should forward the packet. Now, consider the dominant pruning method. Node 4 should determine the forward list among the neighboring nodes. In the example, N(N (4)) = {1, 2, 3, 4, 5, 6, 7, 8}. Among these nodes, N(4) = {1, 2, 3, 4, 5, 7} receives the packet directly from node 4. We should determine the forward list such that N(N(4))-N (4) = {6, 8} are covered.

Fig2: Principle of Source-based Tree in an Ad Hoc Wireless Network

The optimal forward list would be {7}. Based on the same method, we can determine the forward list of node 7 to be 0. Consequently, only two nodes 4, 7 need to forward the packet in order that all the nodes get the packet¹. When the destination node(s) gets the FLOOD_REQ packet it sends a REPLY packet to the source backtracking the path through which it has received the FLOOD_REQ packet. The backward knowledge is obtained by using the following technique. When the source sends the FLOOD_REQ packet to the destination(s) each intermediate node between the source and destination(s) updates the source address field of the FLOOD_REQ packet with its own address. but before that it caches the content of the source address field of the packet which is actually the upstream node address. So, the FLOOD_REQ packet always contains only one address as the source address which is changed at each hop. Thus, this backward information is used to send the REPLY packet back to the originator of the FLOOD_REQ packet. The REPLY packet eventually reaches the original source node creating the multicast tree. So, the multicast tree of a group contains the originator, destination(s) and the nodes in between them. The nodes that are involved in transmitting packets from the source to the destination(s) are called the forwarding nodes. They are not necessarily the members of the same multicast group

RESULT :

Multicast tree is an important task. As any node can be drifted off from its current position at any time in ad hoc network, the routing protocol should also have the mechanism for maintaining the multicast tree. In this regard, NAMP uses the secondary forwarder list scheme. In dominant pruning approach, only those nodes are selected for forwarding the FLOOD_REQ packet, which could be used to flood the packet throughout the whole network with minimum effort. It actually makes an efficient flooding of the FLOOD_REQ packet. Now, to form the Secondary Forwarder List (SFL) for each node along a route, the one-hop neighbor nodes those are also the neighbors (one-hop distance) of the next forwarder node are selected. Each node forming the multicast tree keeps its own SFL and also sends its own SFL to the selected next forwarder along that particular route. The selected forwarder node makes the nodes in that particular SFL know about the next selected forwarder\ node (e.g., the selected forwarder after it along the route). In this way, some neighbor nodes get the knowledge about which node to connect, if there is any link failure.

Fig3 : New branch in M-AODV

Fig4: Dominant pruning method

Fig5: Example Scenario

Fig6 : Formation of SFL

CONCLUSION AND FUTURE WORK:

This research work proposed an efficient routing protocol for mobile ad hoc networks named Neighbor Aware Multicast Routing Protocol (NAMP). We expect that, NAMP improves the performance of the network by taking less time to transfer packets from the source to the destination(s). The tree based protocol also ensures robustness in the network by employing the Secondary Forwarder List (SFL) method. The neighborhood awareness improves the routing mechanism. By using the dominant pruning method for flooding of packets and route creation, it is expected to utilize the bandwidth available for the network.

For the future work, we identify the need to develop a light-weighted but reliable multicast protocol for small groups. It can be applied to the upper level multicast in the routing hierarchy to achieve better reliability in packet delivery

REFERENCES:

1. Aggelou G. and Tafazolli R., “RDMAR: A Bandwidth-Efficient Routing Protocol for Mobile Ad Hoc Networks,” in Proceedings of The 2nd ACM International Workshop on Wireless Mobile Multimedia, Seattle, Washington, pp. 26-33, August 1999.

2. Bertsekas D. and Gallager R., Data Network, Second Edition, Prentice Hall, Englewood Cliffs, New Jersey, 1992.

3. Broch J., Johnson D., and Maltz D., The Dynamic Source Routing in Ad Hoc Wireless Networks, in Mobile Computing, Chapter 5, Kluwer Academic Publishers, 1996.

4. Even S., Graph Algorithms, Computer Science Press, 1979.

5. Garcia-Luna-Aceves J. and Madruga E., “The Core-Assisted Mesh Protocol,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1380-1394,1999.

6. Ko Y. and Vaidya N., “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms,” in Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications (WMCSA '99), New Orleans, USA, pp. 101–110, 1999.

7. Ko Y. and Vaidya N., “GeoTORA: A Protocol for Geocasting in Mobile Ad Hoc Networks,” in Proceedings of the 8th International Conference Network Protocols (ICNP), Osaka, Japan, pp. 240–250, 2000.

8. Lee S., Gerla M., and Chiang C., “On-Demand Multicast Routing Protocol,” in Proceedings of IEEE (WCNC’99), New Orleans, LA., pp. 1298- 1304, 1999.

9. Lim H. and Kim C., “Multicast Tree Construction and Flooding in Wireless Ad Hoc Networks,” in Proceedings of the 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Boston, Massachusetts, USA, pp. 61-68, 2000.

10. Lovasz L., “On the Ratio of Optimal Integral and Functional Covers,” Discrete Mathematics, vol. 13, pp. 383-390, 1975.

11. Maihofer C. and Chrysler D., “A Survey of Geocast Routing Protocols,” IEEE Communications Surveys, vol. 6, no. 2, pp. 32-42, 2004.

12. Murthy S. and Garcia-Luna-Aceves J., “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Netwoks and Applications Journal, Special Issue on Routing in Mobile Communication Networks, pp. 183-197, 1996.

13. Obraczka K. and Viswanath K., Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks, Wireless Networks 7, Kluwer Academic Publishers, http://www.springer.com /east/home?SGWID=5-102-0-0-0&referer=www .wkap.com, 2001.

14. Park V. and Corson M., “A highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” in Proceedings of the IEEE INFOCOM, vol. 3, pp. 1405-1413, 1997.

15. Perkins C. and Bhagwat P., “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” ACM SIGCOMM, pp. 234-244, 1994.

16. Perkins C., Royer E. and Das S., “Ad Hoc on Demand Distance Vector (AODV) Routing,” Internet Draft, http://www.ietf.org/rfc/ rfc3561.txt, IETF, 1999.

17. Royer E. and Perkins C., “Multicast Using Ad Hoc on Demand Distance Vector Routing,” in Proceedings of the ACM Mobicom’99, pp. 207- 218, 1999.

18. Stojmenovic I., Ruhil A., and Lobiyal D., “Voronoi Diagram and Convex Hull-Based Geocasting and Routing in Wireless Networks,” in Proceedings of the Eighth IEEE International Symposium on Computers and Communication 2003 (ISCC’2003), Antalya, Tukey, pp. 51-56, 2001.

19. Toh C., “Long-lived Ad Hoc Routing Based on the Concept of Associativity,” Internet Draft, http://tools.ietf.org/id/draft-ietf-manet-longlivedadhoc- routing-00.txt, IETF, March 1999.

Received on 02.01.2011 Accepted on 06.02.2011

Research J. Engineering and Tech. 2(2): April-June 2011 page 61-65